/**
 * 
 */
package solution.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import junit.framework.Assert;
import lib.tree.BNode;
import lib.tree.TreeUtil;
import lib.util.Mutable;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class SortedListToBST {
	BNode list;

	/**
	 * convert a BST to sorted list.
	 * 
	 * @param size
	 * @return the BST
	 */
	public BNode BSTToList(BNode root) {
		BNode head = new BNode(); // create the head node
		list = head; // list is visible to the whole recurse stack.
		BSTToListrec(root);
		return head;
	}

	private void BSTToListrec(BNode root) {
		if (root == null)
			return;

		// link the left branch.
		BSTToListrec(root.left);

		// visit the root.
		BNode right = root.right;
		root.left = root.right = null;
		list.next = root;
		root.prev = list;
		list = list.next;

		// link the right branch.
		BSTToListrec(right);
	}

	public BNode sortedListToBST(BNode head, int size) {
		if (head == null)
			return null;

		list = head.next;
		return sortedListToBSTrec(new Mutable<Integer>(size));
	}

	/**
	 * convert a sorted list to a balanced BST. (left <= root <= right)
	 * 
	 * @param size
	 * @return the BST
	 */
	private BNode sortedListToBSTrec(Mutable<Integer> size) {
		if (size.getValue() <= 0 || list == null) {
			size.setValue(0);
			return null;
		}

		Mutable<Integer> leftSize = new Mutable<Integer>(size.getValue() / 2);
		BNode left = sortedListToBSTrec(leftSize);
		if (list == null) {
			size.setValue(leftSize.getValue());
			return left;
		}

		// root, grab current value
		BNode root = list;

		list = list.next;
		if (list != null) {
			list.prev = null;
		}

		root.left = left;
		root.prev = root.next = root.right = null;
		if (list == null) {
			size.setValue(leftSize.getValue() + 1);
			return root;
		}

		Mutable<Integer> rightSize = new Mutable<Integer>(size.getValue() - 1
				- leftSize.getValue());
		root.right = sortedListToBSTrec(rightSize);

		size.setValue(leftSize.getValue() + 1 + rightSize.getValue());
		return root;
	}

	@Test
	public void test() {
		List<Integer> lst = new ArrayList<Integer>();
		TreeUtil treeUtil = new TreeUtil();
		for (int k = 0; k < 50; k++) {
			lst.clear();
			// generate sorted list of different size and value.
			for (int i = 0; i < Math.random() * 100 + 1; i++) {
				lst.add((int) (Math.random() * 10));
			}
			Collections.sort(lst);
			BNode head = new BNode(), p = head;
			for (Integer num : lst) {
				BNode nd = new BNode();
				nd.value = num;
				nd.prev = p;
				p.next = nd;
				p = nd;
			}

			String s1 = head.toListStr();

			BNode tree = sortedListToBST(head, lst.size());
			Assert.assertTrue(treeUtil.isBST2(tree));
			// String s2 = tree.toTreeStr();

			BNode list = BSTToList(tree);
			String s3 = list.toListStr();

			Assert.assertEquals(s1, s3);
		}
	}
}
